class Solution {
public:
    /**
     * 
     * @param x int整型 
     * @return int整型
     */
    /*
    将左边界定为1，右边界定为x，比较中间元素与x大小关系
    mid*mid<=x&&(mid+1)*(mid+1)>x 返回mid
    mid*mid>x   right=mid-1;
    否则 left=mid+1
    */
    int sqrt(int x) {
        // write code here
        if(x==1)
            return 1;
        int l=1,r=x;
        while(r>=l)
        {
            int mid=(l+r)/2;
            if(mid<=x/mid&&(mid+1)>x/(mid+1)) return mid;
            if(mid>x/mid) r=mid-1;
            else 
                l=mid+1;
        }
        return 0;
    }
};